Code

Let's get straight into it.

Part 1 only exists so you build the tools to detect the polygon you'll be working on in part 2. The only real "snag" (if can even call it that) is that you have to pick a starting direction from the initial tile.

Part 2 requires us to count the number of tiles that are inside of the loop. Floodfills are (kind of) foiled by the rules of the puzzle. I'm sure a solution based on those is possible, just seems like too much effort...

Anyway, I started by reminding myself on how to tell if a point is inside a shape.

Yeah, that'll do. I settled on casting a ray at a 45 degree angle down to the right; because that way it will never be parallel to any of the pipes, and it's easy to step along it.

One thing to keep in mind is that with an incline like that, is L and 7 bends are intersected twice—the line we're (virtually) drawing hits both before and after the bend. Because of that, if we ever hit the starting point, we have to reverse-engineer what kind of bend it is, because it might count as either 1 or 2 intersections.

Taking all that into account, I came up with this function to check whether a point is inside my shape:

type Pos = (i32, i32);

fn is_inside(map: &[&[u8]], shape: &HashSet<Pos>, (x, y): Pos, (max_x, max_y): Pos) -> bool {
    // If we're on the shape, we can't be inside.
    if shape.contains(&(x, y)) {
        return false;
    }

    // Count intersections of shape with a line going down-right at a 45 degree angle.
    let steps = i32::min(max_x - x, max_y - y);
    let mut intersects = 0;
    for n in 1..=steps {
        if shape.contains(&(x + n, y + n)) {
            intersects += match map[(y + n) as usize][(x + n) as usize] {
                b'L' | b'7' => 2,
                b'-' | b'|' | b'F' | b'J' => 1,
                b'S' => {
                    // We unfortunately have to check which kind of bend the 'S' tile is.
                    let (x, y) = ((x + n) as usize, (y + n) as usize);
                    let left = b"-L7".contains(&map[y][x - 1]);
                    let top = b"|F7".contains(&map[y - 1][x]);
                    let right = b"-7J".contains(&map[y][x + 1]);
                    let bottom = b"|LJ".contains(&map[y - 1][x + 1]);

                    1 + usize::from((top && right) || (left && bottom))
                }
                _ => 0,
            };
        }
    }
    intersects % 2 == 1
}

I chose to represent the shape as simply a set of points. Before I call this, I calculate the smallest rectangle containing the entire shape, and then do this check for every point inside that rectangle; max_x and max_y are passed in so I know how many steps to take along the raycast.

That's pretty much it.

Before settling on this working solution, I tried to make it work with a ray cast straight downwards, but accounting for contiguous vertical segments and other such nonsense wasn't worth it.

Built with --release optimizations, it currently runs in 6 milliseconds for me. I'm convinced I could get it below a millisecond by constructing an "intersection map" straight away—that is, a 2D array where each element is the number of intersections if a ray was cast from there. Constructing that from the bottom right would probably be faster than casting a full ray from every position... but I'm hungry, so nah.

Update about an hour later

Ok, I couldn't help myself. I implemented a more efficient version that hits less than a millisecond with --release optimizations. I was halfway through implementing some complicated thing before realizing that flipping the ray simplifies the implementation immensely.

Yeah, now I'm casting the ray up and to the left instead. This allows me to walk down-right along every ray and cover all points on it in one fell swoop.

In addition, my shape is no longer a hashset, but simply a nested array/Vec. Turns out, the map is small enough that allocating all that stuff is perfectly fine and more than makes up for the time you would spend on hash lookups instead.

let mut inside_points = 0;
for x in -(h as i32)..w as i32 {
	// Calculate the x range the diagonal intersects the rectangle in.
	let min_step = 0.max(-x);
	let max_step = i32::min(w as i32 - x, h as i32);

	// Run along the diagonal.
	let mut next_is_inside = false;
	for n in min_step..max_step {
		if shape[n as usize][(x + n) as usize] {
			let (x, y) = ((x + n) as usize, n as usize);
			next_is_inside ^= match map[y][x] {
				b'-' | b'|' | b'F' | b'J' => true,
				b'S' => {
					// We unfortunately have to check which kind of bend the 'S' tile is.
					let left = b"-FL".contains(&map[y][x - 1]);
					let top = b"|F7".contains(&map[y - 1][x]);
					let right = b"-7J".contains(&map[y][x + 1]);
					let bottom = b"|JL".contains(&map[y + 1][x]);

					!((top && right) || (left && bottom))
				}
				_ => false,
			};
		} else if next_is_inside {
			inside_points += 1;
		}
	}
}

Ok(inside_points)

Also, I no longer find the smallest rectangle. This method is fast enough that all the rectangle stuff simply complicates it for no real further gain. "The rectangle" is now simply the entire map. And as a final change, I don't really keep track of the total amount of intersections, just if there's an odd amount of them. Hence the ^= (xor assign); all branches of the match return whether there's been an odd number of intersections.

I'm very happy with this solution now.

However, I am still hungry, possible more so than an hour ago...